Security modules represented by IC cards have guaranteed security by difficulties of reverse engineering, and computational difficulties of cryptanalysis. As methods for making the reverse engineering difficult, use of nonstandard cell, arrangement of dummy circuit, scrambled arrangement of memory, scrambled arrangement of bus, cutoff of test pad from product chip, and the like are performed (refer to W. Rankl & W. Effing, Smart Card Handbook Second Edition, pp. 412-420, WILEY, 2000, ISBN 0-471-98875-8 (Non-patent Document 1)).
With regard to the difficulties of cryptanalysis, security is based upon that the computation amount necessary for cryptanalysis is so sufficiently large that impossible to decrypt within an acceptable time. With regard to the computational difficulties, security is based upon the bit length of a secret key, and as the key length becomes long, so the computation amount necessary for decryption becomes large. Along with the progress of semiconductor technologies, the computer power available increases, and the safe key bit length has been getting longer as time goes by.
As an attack that is uninfluenced by countermeasures by such reverse engineering and the computational difficulties, there exists Differential Fault Analysis. Differential Fault Analysis is a method where a computational fault is made to occur in a chip in some way, and by use of the difference between the correct computational result and the wrong computational result, the key information is presumed, and attacks have been developed to many cryptosystems. The feature of the attack is that the time necessary for attack is extremely short. For example, it is known that in the Differential Fault Analysis of RSA cryptography using CRT algorithm, irrespective of the key length, if only one computational fault is obtained, from the greatest common divisor of the difference between the correct value and the fault value and the modulo N of the public key, a secret prime number p can be obtained, and a secret key can be calculated from the result (for example, refer to D. Boneh, R. A. Demillo, and R. J. Lipton: On the Importance of Checking Cryptographic Protocols for Faults, EUROCRYPT '97, Vol. 1233 of Lecture Notes in Computer Science, pp. 37-51, Springer-Verlag, 1997 (Non-patent Document 2)).
It is reported by E. Biham et al. that in DES cryptosystem used widely as a secret key cryptosystem, if several to several tens of correct computational results and fault results are obtained, a secret key can be obtained (E. Biham, A. Shamir, “A New Cryptanalytic Attack on DES,” http://www.jya.com/dfa.htm, 1996). In also AES encryption proposed as a successor cryptosystem of DES cryptosystem, a method where if fault computations are made to occur in one byte among the halfway of computation, a key can be obtained from two fault computational results is proposed by J. J. Quisquater et al. (for example, refer to G. Piret and J. J. Quisquater: A Differential Fault Attack Technique against SPN Structures, with Application to the AES and KHAZAD, CHES 2003, LNCS 2779, pp. 78-88, Springer-Verlag, 2003 (Non-patent Document 3)). These attacks are characterized by that the computational amount necessary for attack is fixed irrespective of the length of cryptographic key, or in proportion with only the bit length of cryptographic key and the computational amount is extremely small.
As Differential Fault Analysis countermeasures, there are proposed, according to cryptosystems, (1) a method where computation is made twice, and it is confirmed whether the two computational results are equal; (2) a method where recalculation is made by inverse computation; and (3) a method where integrity of computations is checked by use of degenerate representation of residue field and parity, and so on. However, in these countermeasures, it is necessary to carry out a process for checking the integrity of computational results, and if the checking process is not carried out, Differential Fault Analysis can be possible.
As technologies to detect a control flow error, there are known the following first to fifth methods.
The first method is a method where the address designated as a destination of jump instruction existing in a program is stored beforehand as jump destination address information, and at the moment when the jump instruction is executed, it is checked that the address set as a program counter after execution of the jump instruction is included in the stored jump destination address information, and thereby the transition of an incorrect control flow is detected (for example, refer to Japanese Patent Application Laid-Open Publication No. 10-63541 (Patent Document 1) and Japanese Patent Application Laid-Open Publication No. 9-146789 (Patent Document 2)).
The second method is a method where a memory area storing a program and a memory area not storing a program are stored as flag information, or the valid range of address of a program counter is limited, and the case when the program counter indicates the memory area not storing a program is detected to judge it as a fault (for example, refer to Japanese Patent Application Laid-Open Publication No. 10-003407 (Patent Document 3)).
The third method is a method where each program area is numbered, and it is checked whether a value transits as determined sequence (for example, refer to Japanese Patent Application Laid-Open Publication No. 6-324914 (Patent Document 4)).
The fourth method is a method where a program is divided into modules beforehand, each module is numbered with a unique number, and at execution, numbers are updated along execution, and it is checked whether the unique numbers in module become identical to the expected values obtained in the case when modules are executed in the supposed sequence (for example, refer to Japanese Patent Application Laid-Open Publication No. 60-3045 (Patent Document 5) and Japanese Patent Application Laid-Open Publication No. 57-199056 (Patent Document 6)).
It is a method where it is checked whether the numbers are identical, and if they are not identical, it is judged as a fault (for example, refer to Japanese Patent Application Laid-Open Publication No. 9-319621 (Patent Document 7)).